package com.hfb.mashibing.alip8.diamondsquarealgorithm.class11;

/**
 * 汉诺塔问题:
 * 规则——只能小盘子压大盘子
 *
 * N 层圆盘：左——>右
 * 三大步骤：
 *  1、1~n-1层圆盘 左——>中间
 *  2、N层圆盘 左——>右
 *  3、1~N-1层圆盘 中——>右
 *
 */
public class Code01_Hanoi {

    public static void main(String[] args) {
        int n = 3;
        hanoi1(n);
        System.out.println("===========================");
        hanoi2(n);
    }
    public static void hanoi1(int n){
        leftToRight(n);
    }
    public static void leftToRight(int n){
        if (n==1){
            System.out.println("Move 1 from left to right");
            return;
        }
        leftToMid(n-1);
        System.out.println(String.format("Move %s from left to right", n));
        midToRight(n-1);
    }
    public static void leftToMid(int n){
        if (n==1){
            System.out.println("Move 1 from left to mid");
            return;
        }
        leftToRight(n-1);
        System.out.println(String.format("Move %s from left to mid", n));
        rightToMid(n-1);
    }
    public static void rightToMid(int n){
        if (n==1){
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightToLeft(n-1);
        System.out.println(String.format("Move %s from right to mid", n));
        leftToMid(n-1);
    }
    public static void midToRight(int n){
        if (n==1){
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n-1);
        System.out.println(String.format("Move %s from mid to right", n));
        leftToRight(n-1);
    }

    public static void midToLeft(int n){
        if (n==1){
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n-1);
        System.out.println(String.format("Move %s from mid to left", n));
        rightToLeft(n-1);
    }

    public static void rightToLeft(int n){
        if (n==1){
            System.out.println("Move 1 from right to left");
            return;
        }
        rightToMid(n-1);
        System.out.println(String.format("Move %s from right to left", n));
        midToLeft(n-1);
    }

    /**
     * N 层圆盘：左——>右
     * 三大步骤：
     *  1、1~n-1层圆盘 from——>other
     *  2、N层圆盘 from——>to
     *  3、1~N-1层圆盘 other——>to
     * @param n
     */
    public static void hanoi2(int n){
        if (n > 0){
            func(n, "left", "right", "mid");
        }
    }
    // 1~i 圆盘 目标是from->to, other是另外一个
    private static void func(int n, String from, String to, String other) {
        if(n==1){ // N层圆盘 from——>to
            // base
            System.out.println(String.format("Move %s from %s to %s", n,from,to));
        } else {
            func(n-1,from, other, to); // 1、1~n-1层圆盘 from——>other
            System.out.println(String.format("Move %s from %s to %s", n,from,to));
            func(n-1,other, to, from); // 3、1~N-1层圆盘 other——>to
        }
    }
    // 非递归
    public static class Record {
        String from ;
        String other;
        String to;

        public Record(String from, String other, String to) {
            this.from = from;
            this.other = other;
            this.to = to;
        }
    }
    public static void hanoi3(int n){
        String from = "左";
        String other = "中";
        String to = "右";

    }


}
